Conventionally, there has been the problem of leakage and tampering of data and others exchanged over the Internet or the like. For the solution to this problem, a cryptosystem of encrypting data and others to transmit it to the receiving end has been adopted.
The cryptosystem is classified into a common-key cryptosystem and a public-key cryptosystem. The public-key cryptosystem is mainly adopted because of easier key management, lower risk of data leakage, and other reasons.
The typical example of the public-key cryptosystem is the RSA encryption scheme.
The RSA encryption scheme is a public-key cryptosystem using as one of public keys a product n=pq, where p and q are prime numbers generated as a substantial private key, and employing the nature of the easiness of finding n from p and q, but the difficulty of finding two prime numbers p and q from n.
Thus, by publicly revealing n as one of public keys, everyone can generate a ciphertext, but it is very difficult to find two large prime numbers p and q for decryption of the ciphertext. From this point, it can be said that security of data transmitted by the RSA encryption scheme is extremely high.
However, although the conventional RSA encryption scheme as described above has a high performance in terms of data secrecy and has a simple algorithm, its security depends on the difficulty of factoring a product n of two prime numbers p and q. Therefore, it is necessary to use about 200-digit n in the decimal system, and there is the problem that it is very difficult to perform modulo n exponentiation, which are necessary for encryption and decryption processes.
Moreover, the RSA encryption scheme is of a multiplicative property, which results in a security problem that three signatures can be generated from two signatures.